/*
*	分治
*/

/****快排****/

//颜色分类
//https://leetcode.cn/problems/sort-colors/
// class Solution {
// public:
//     void sortColors(vector<int>& nums) {
//         int n = nums.size();
//         int left = -1, right = n, pos = 0;
//         int key = 1;
//         while (pos < right)
//         {
//             if (nums[pos] < key) swap(nums[pos++], nums[++left]);
//             else if (nums[pos] == key) ++pos;
//             else if(nums[pos] > key) swap(nums[pos], nums[--right]);
//         }
//     }
// };


//数组中的第k个最大元素
//https://leetcode.cn/problems/kth-largest-element-in-an-array/submissions/
// class Solution {
// public:
//     int findKthLargest(vector<int>& nums, int k)
//     {
//         srand(time(NULL));
//         return qsort(nums, 0, nums.size() - 1, k); //找第k大的数 边找边排序
//     }

//     int qsort(vector<int>& nums, int l, int r, int k)
//     {
//         if (l == r) return nums[l];
//         int key = nums[rand()%(r-l+1)+l];
//         int left = l - 1, right = r + 1, pos = l;
//         while (pos < right)
//         {
//             if (nums[pos] < key) swap(nums[pos++], nums[++left]);
//             else if (nums[pos] == key) ++pos;
//             else swap(nums[pos], nums[--right]);
//         }
//         //此时划分出了三段
//         //        <key            ==key           >key
//         //   倒数a大的元素       前b大的元素      前a大的元素      描述区间元素个数
//         //     [l,left]      [left+1,right-1]   [right,r]
//         //如果 k<c 则表示前a大的元素中有第k大的元素 去前a大区间中找即可
//         //如果 k<=c+b 则b中就是该元素 返回key
//         //如果 前两个都不满足 则在a中 此时去 [l,left] 中找 k-b-c 个元素即可 (因为直接找k，[l,left]中元素个数可能是<k个的)
//         if ((r-right+1)>=k) return qsort(nums, right, r, k);
//         else if ((r-left)>=k) return key;
//         return qsort(nums, l, left, k-(r-left)); 
//     }
// };


//库存管理III
//https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/submissions/
// class Solution {
// public:
//     vector<int> inventoryManagement(vector<int>& stock, int cnt) {
//         srand(time(nullptr));
//         qsort(stock,0,stock.size()-1,cnt);
//         return {stock.begin(),stock.begin()+cnt};
//     }

//     void qsort(vector<int>& nums, int l, int r, int k)
//     {
//         if (l >= r) return;
//         int key = nums[rand()%(r-l+1)+l];
//         int left = l - 1, right = r + 1, pos = l;
//         while (pos < right)
//         {
//             if (nums[pos] < key) swap(nums[pos++], nums[++left]);
//             else if (nums[pos] == key) ++pos;
//             else swap(nums[pos], nums[--right]);
//         }
//         //我们只需要将 较小的前k个元素 排在[l,left]区间即可
//         if ((left-l+1) >= k) qsort(nums, l, left, k);
//         else if ((right-l)>=k) return; //如果在前两个区间中 则直接返回即可
//         return qsort(nums, right, r, k-(right-l)); //否则去最后一个区间中查找 第 k-(right-l)
//     }
// };


//库存管理III
//https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/submissions/
// class Solution {
// public:
//     vector<int> inventoryManagement(vector<int>& stock, int cnt) {
//         srand(time(nullptr));
//         qsort(stock,0,stock.size()-1,cnt);
//         return {stock.begin(),stock.begin()+cnt};
//     }

//     void qsort(vector<int>& nums, int l, int r, int k)
//     {
//         if (l >= r) return;
//         int key = nums[rand()%(r-l+1)+l];
//         int left = l - 1, right = r + 1, pos = l;
//         while (pos < right)
//         {
//             if (nums[pos] < key) swap(nums[pos++], nums[++left]);
//             else if (nums[pos] == key) ++pos;
//             else swap(nums[pos], nums[--right]);
//         }
//         //我们只需要将 较小的前k个元素 排在[l,left]区间即可
//         if ((left-l+1) >= k) qsort(nums, l, left, k);
//         else if ((right-l)>=k) return; //如果在前两个区间中 则直接返回即可
//         return qsort(nums, right, r, k-(right-l)); //否则去最后一个区间中查找 第 k-(right-l)
//     }
// };



/****归并****/

//排序数组-归并排序
//https://leetcode.cn/problems/sort-an-array/submissions/
// class Solution {
// public:
//     vector<int> sortArray(vector<int>& nums) 
//     {
//         vector<int> tmp(nums.size());
//         MergoSort(nums,tmp,0,nums.size()-1);
//         return nums;
//     }

//     void MergoSort(vector<int>& nums,vector<int>& tmp,int begin,int end)
//     {
//         if(begin>=end) return;

//         int mid = (begin+end)/2;

//         int left1 = begin,right1 = mid;
//         int left2 = mid+1,right2 = end;
//         MergoSort(nums,tmp,left1,right1);
//         MergoSort(nums,tmp,left2,right2);
//         int pos = begin;
//         while(left1<=right1 && left2<=right2)
//         {
//             if(nums[left1] > nums[left2]) tmp[pos++] = nums[left2++];
//             else tmp[pos++] = nums[left1++];
//         }

//         while(left1<=right1) tmp[pos++] = nums[left1++];
//         while(left2<=right2) tmp[pos++] = nums[left2++];
        
//         memcpy(&nums[begin],&tmp[begin],sizeof(int)*(end-begin+1));
//     }
// };



//交易逆序对的总数
//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/submissions/
// class Solution {
// public:
//     int reversePairs(vector<int>& record) {
//         vector<int> tmp(record.size());
//         return MergoSort(record,tmp,0,record.size()-1);
//     }

//     //将数组分为两段 分别统计两段数组中的逆序对并返回且完成排序
//     int MergoSort(vector<int>& nums,vector<int>& tmp,int l,int r)
//     {
//         if(l>=r) return 0;
//         int mid = (l+r)/2;

//         int ret = 0;
//         ret += MergoSort(nums,tmp,l,mid);
//         ret += MergoSort(nums,tmp,mid+1,r);

//         int tpos = l;
//         int pos1 = l,pos2 = mid+1;
        
//         while(pos1<=mid && pos2<=r)
//         {
//             //升序
//             // if(nums[pos1] <= nums[pos2]) tmp[tpos++] = nums[pos1++];
//             // else
//             // {
//             //     (ret += mid-pos1+1);
//             //     tmp[tpos++] = nums[pos2++];
//             // }

//             //降序写法 防止统计较小的数
//             if(nums[pos1] <= nums[pos2]) tmp[tpos++] = nums[pos2++];
//             else
//             {
//                 (ret += r-pos2+1);
//                 tmp[tpos++] = nums[pos1++];
//             }
//         }
//         while(pos1<=mid) tmp[tpos++] = nums[pos1++];
//         while(pos2<=r) tmp[tpos++] = nums[pos2++];

//         memcpy(&nums[l],&tmp[l],sizeof(int)*(r-l+1));
//         return ret;
//     }
// };


//计算右侧小于当前元素的个数
//https://leetcode.cn/problems/count-of-smaller-numbers-after-self/submissions/
// class Solution {
//     vector<int> ret;
//     vector<int> tmp;
//     int index[500010];
//     int tmpindex[500010];
// public:
//     vector<int> countSmaller(vector<int>& nums) 
//     {
//         int n = nums.size();
//         ret.resize(n);
//         tmp.resize(n);
//         for(int i = 0;i<n;++i) index[i]=i; //记录原始下标
//         MergoSort(nums,0,nums.size()-1);
//         return ret;
//     }

//     void MergoSort(vector<int>& nums,int l,int r)
//     {
//         if(l>=r) return;

//         int mid = (l+r)/2;
//         MergoSort(nums,l,mid);
//         MergoSort(nums,mid+1,r);

//         int pos = l;
//         int pos1 = l,pos2 = mid+1;

//         while(pos1 <= mid && pos2 <= r)
//         {
//             if(nums[pos1] > nums[pos2])
//             {
//                 //如果当前左区间的值比右区间的值大 因为是降序 则右区间值开始后面所有值都比该值小
//                 //此时pos1位置的值 和其最开始的下标都在index中
//                 ret[index[pos1]] += r-pos2+1;
//                 tmpindex[pos] = index[pos1]; //将原始下标一起写入tmpindex中
//                 tmp[pos++] = nums[pos1++];
//                 //原始下标随原数排序一起移动
//             }
//             else
//             {
//                 tmpindex[pos] = index[pos2];
//                 tmp[pos++] = nums[pos2++];
//             }
//         }
//         while(pos1 <= mid) 
//         {
//             tmpindex[pos] = index[pos1];
//             tmp[pos++] = nums[pos1++];
//         }
//         while(pos2 <= r) 
//         {
//             tmpindex[pos] = index[pos2];
//             tmp[pos++] = nums[pos2++];
//         }
//         memcpy(&nums[l],&tmp[l],sizeof(int)*(r-l+1));
//         memcpy(&index[l],&tmpindex[l],sizeof(int)*(r-l+1));
//     }
// };


//翻转对
//https://leetcode.cn/problems/reverse-pairs/submissions/
// class Solution {
// public:
//     int reversePairs(vector<int>& nums) {
//         vector<int> tmp(nums.size());
//         return MergoSort(nums,tmp,0,nums.size()-1);
//     }

//     int MergoSort(vector<int>& nums,vector<int>& tmp,int l,int r)
//     {
//         if(l>=r) return 0;

//         int mid = (l+r)/2;

//         //先计算左右区间的翻转对
//         int ret = 0;
//         ret += MergoSort(nums,tmp,l,mid);
//         ret += MergoSort(nums,tmp,mid+1,r);

//         //计算本区间的翻转对
//         int pos1 = l,pos2 = mid+1;
//         //如果是升序 则需要在右区间找一个数 如果左区间的某个数的一半 比右区间的数要大 则左区间数后面的数全部比右区间该数要大
//         //如果是降序 则需要在左区间固定一个数 如果右区间中某一个数的两倍比左区间数要小 则右区间数后面的数全部比左区间该数小
//         // while(pos2 <= r) //升序 先固定右区间的一个数
//         // {
//         //     //在左区间中找一个数的一半 比右区间的数大 则此时左区间从该数开始到mid的所有数的一半都比右区间的该数大 也就是大于右区间数的两倍
//         //     while(pos1<=mid && nums[pos2]>=nums[pos1]/2.0) ++pos1;
//         //     if(pos1 > mid) break;
//         //     ret += mid-pos1+1;
//         //     ++pos2;
//         // }

//         while(pos1 <= r) //降序 先固定左区间的一个数
//         {
//             //在右区间中找一个数的两倍 比左区间的数小 则右区间数到r的所有数两倍都比左区间小
//             while(pos2<=r && nums[pos2]>=nums[pos1]/2.0) ++pos2;
//             if(pos1 > mid) break;
//             ret += r-pos2+1;
//             ++pos1;
//         }
//         int pos = l;
//         pos1 = l,pos2 = mid+1;
//         //while(pos1<=mid&&pos2<=r) tmp[pos++] = nums[pos1]<nums[pos2]?nums[pos1++]:nums[pos2++]; //降序排序
//         while(pos1<=mid&&pos2<=r) tmp[pos++] = nums[pos1]>nums[pos2]?nums[pos1++]:nums[pos2++]; //升序排序
//         while(pos1<=mid) tmp[pos++] = nums[pos1++];
//         while(pos2<=r) tmp[pos++] = nums[pos2++];
//         memcpy(&nums[l],&tmp[l],sizeof(int)*(r-l+1));
//         return ret;
//     }
// };


